Graphics rendering systems create images of objects which are combined in a visual scene. An object is a computer readable specification of appearance attributes which, when used to create a display image, has the appearance of physical substance, and a scene is a collection of objects distributed in an area to be represented in a display image. In a two dimensional graphics rendering system a display image is constructed based on the location and orientation of two dimensional objects in a scene. For a three dimensional graphics rendering system, three dimensional objects are placed in a three dimensional scene with a three dimensional coordinate system, and a camera is defined by at least a location and a direction of view relative to the scene. Rendering is the process of creating a display image based on the objects which would be visible to a camera viewing a scene if it were real, and placing this display image in memory, typically a frame buffer. The display image is composed of an array of picture elements, or pixels, which each exhibit a color. In real-time rendering systems, the display image is displayed, typically on a display screen, while a later display image is being constructed.
High speed rendering systems typically rely on combinations of simple polygons, referred to as primitives, to build models of more complex objects. Such rendering systems are generally optimized to render primitives into frame buffers quickly. Triangles are commonly used as primitives, since objects of arbitrary complexity may be composed of triangles.
Rendering systems commonly use two types of "clipping" when creating display images based on three dimensional scenes. One common clipping method is hither plane clipping. When a rendering system creates a two dimensional representation of a three dimensional scene, it does so by determining the projection of three dimensional primitives within the scene on an image plane. A portion of the image plane corresponds to the display image, and the primitives projected within this portion of the image plane appear in the display image. The projection process usually involves simple geometry which would allow primitives to be projected on the image plane from either side of the image plane. Generally, however, it is desired that only primitives on one side (the "front side") of the image plane be rendered, since primitives on the other side (the "back side") are behind the camera and should be out of the field of view. In order to prevent primitives on the back side of the image plane from being projected on the image plane, hither plane clipping is ordinarily employed. A hither plane is generally parallel to the image plane and marks the boundary between primitives which are drawn and primitives which are not drawn. The hither plane is often located a small distance in front of the image plane, to prevent the attempted projection of points lying within the image plane to the image plane, as the projection geometry generally cannot handle this. The hither plane is between the location of the camera and the drawn objects. Primitives on the back side of the hither plane are not projected on the image plane, and those on the front side are. Primitives which cross the hither plane are subjected to a clipping process, wherein the primitive is modified so as to not extend to the back side of the hither plane. The clipping process can be time consuming, however, and the rendering speed of a system can be adversely affected when even a few primitives cross the hither plane.
The other type of clipping commonly used by rendering systems is image plane clipping. A rendering system typically projects primitives onto an image plane by determining the location of pixels in the image plane which are intersected by lines projected from the primitives to the camera. Because these pixels might not all lie within the area of the image plane which represents the display image, rendering systems often need to determine whether each pixel location of a projection is within the display image area before attempting to render that pixel to the display image. Routines used by the rendering system to determine a display memory address from a pixel coordinate location are usually highly optimized and often will generate erroneous results if given a pixel coordinate location which is outside the bounds of what is expected. If pixels outside the display image area given to a rendering routine which expects only pixels located within the display image area, there may be unexpected results. Testing the location of each pixel prior to drawing it to the display image, however, would slow the rendering process unacceptably.
To overcome this problem many rendering systems use display image clipping. Display image clipping is used to modify image plane projections which lie partially within the display image area of the image plane and partially outside the display image area of the image plane. The projections are modified so that the modified projection lies completely within the display image area of the image plane and has the appearance of that portion of the original projection which was in the display image area. Projections of simple polygons can be quickly tested to determine whether they are within the display image portion of the image plane, outside the display image portion of the image plane, or whether they cross the boundaries of the display image portion of the image plane. Those projections entirely within the display image portion can be rendered, and those entirely outside the display image portion can be ignored. Only those which are partially in and partially out of the display image portion of the image plane need to be clipped. Typical polygon clipping algorithms include those described in Sutherland, I. E., et al., "Reentrant Polygon Clipping," CACM, 17(1), January 1974, 32-42, Weiler, K., "Polygon Comparison Using a Graph Representation," SIGGRAPH 80, 10-18, and Liang, Y-D., and B. A. Barsky, "An Analysis and Algorithm for Polygon Clipping," CACM, 26(11), November 1983, 868-877. The process of clipping the projections, however, is time consuming, and the rendering speed can be significantly degraded if even a few of the primitive projections are subjected to display image clipping.
What is needed is a system which achieves results similar to those achieved through hither plane clipping and display image clipping without taking as much time as these clipping methods.